/*
 * @Author: szx
 * @Date: 2022-05-22 14:48:02
 * @LastEditTime: 2022-05-22 15:01:13
 * @Description:
 * @FilePath: \leetcode\面试题\08\01\01.js
 */
/**
 * @param {number} n
 * @return {number}
 */
var waysToStep = function (n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    let dp1 = 1,
        dp2 = 2,
        dp3 = 4;
    tmp = 0;
    const MOD = 1000000007;
    for (let i = 4; i <= n; i++) {
        tmp = (dp3 + dp2 + dp1) % MOD;
        dp1 = dp2;
        dp2 = dp3;
        dp3 = tmp;
    }
    return dp3;
};
